package com.zj.leetcode.medium.dynamicProgramming;

import java.util.Arrays;

/**
 * @program: algorithm
 * @description: 零钱兑换
 * 322 coin-change
 * @author: Zhang Bo
 * @create: 2022-05-11 14:18:34
 **/
public class CoinChange {
    public static void main(String[] args) {
//        int amount = 11;
//        int[] coins = {1,2,5};

        int amount = 6249;
        int[] coins = {186, 419, 83, 408};
        Solution solution = new CoinChange().new Solution();
        System.out.println(solution.coinChange(coins, amount));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * [186,419,83,408]
         * 6249
         *
         * @param coins
         * @param amount
         * @return
         */
        public int coinChange(int[] coins, int amount) {
            int max = Integer.MAX_VALUE;
            int[] dp = new int[amount + 1];

            Arrays.fill(dp, max);

            dp[0] = 0;
            for (int i = 0; i < coins.length; i++) {

                for (int j = coins[i]; j <= amount; j++) {

                    if (dp[j - coins[i]] != max) {

                        dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                    }
                }
            }
            return dp[amount] == max ? -1 : dp[amount];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}